package com.gorkr.dp;

import org.junit.jupiter.api.Test;

/**
 * 。所以根据贪心算法，就尽量将原数拆成更多的 3，然后再拆成更多的 2，保证拆出来的整数的乘积结果最大。
 *
 *  取余不行的原因是 大数溢出了
 * @author gorkr
 * @date 2022/07/28 11:05
 **/
public class M343IntegerBreak {
    public int cuttingRope(int n) {

        if (n <= 3) {
            return n - 1;
        }
        int p = 1000000007;

        int shang = n / 3;
        int yushu = n % 3;

        if (yushu == 0) {
            return (int) ((Math.pow(3, shang)) % p);
        } else if (yushu == 1) {
            return (int) ((Math.pow(3, shang - 1) * 4) % p);
        } else {
            return (int) ((Math.pow(3, shang) * 2) % p);
        }
    }


    @Test
    public void test() {
        int p = 1000000007;
        System.out.println(cuttingRope(120));

    }
}
    